package com.kaizen.leet169;

import java.util.Arrays;

/**
 * 169. 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
 *
 * 官方最优解
 * 此处没记录随机化方法
 * @author kaizen
 * @date 2020/5/9 14:01
 */
public class Solution {

    /**
     * 方法1 排序
     * 先排序
     * 考虑两种边界情况
     * 1.众数为最小值 0 0 0 3 4（000012）
     * 2.众数为最大值 1 2 3 3 3（123333）
     * n/2的位置都为众数
     *
     * @param nums
     * @return
     */
    public int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    /**
     * 分治法
     * n = N(0-2/n) + N(2/n+1) 出现次数最多的 
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        return majorityElement2(nums, 0, nums.length-1);
    }

    public int majorityElement2(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int mid = (r-l)/2 + l;
        int left = majorityElement2(nums, l, mid);
        int right = majorityElement2(nums, mid+1, r);
        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }
        int leftCount = countInRange2(nums, left, l, r);
        int rightCount = countInRange2(nums, right, l, r);
        return leftCount > rightCount ? left : right;
    }

    /**
     * 获取次数最多的
     * @param nums
     * @param num
     * @param lo
     * @param hi
     * @return
     */
    private int countInRange2(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }


    /**
     * 摩尔投票法
     * 从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个
     * @param nums
     * @return
     */
    public int majorityElement3(int[] nums) {
        int count = 0;
        int res = 0;
        for (int num : nums) {
            if (count == 0) {
                res = num;
            }
            if (res == num) {
                count ++;
            }else {
                count --;
            }
        }
        return res;
    }

}
